const handleCombin = function(data) {
  return {
    id: window.uuid(),
      favorite: false,
      data: [...data],
  }
}

const backtrack = function (list, track, used, count, res, start, length, isGroup, need, max, validator) {
  if (validator(track)) {
    res.push(handleCombin(track));
  }
  if (res.length > max) return; // 组合太多了
  if (track.length === length) return;

  for (let i = start; i < list.length; i++) {
    const c = list[i];
    if (used[c.direction] === 2) continue; // 左 上 右 最多各 2个
    if(isGroup) {
      let cCount = count[c.name] || 0;
      if(cCount === need[c.name]) continue;// 不能大于指定数量
    }

    track.push(c);
    used[c.direction]++;
    count[c.name] = (count[c.name] || 0) + 1;
    backtrack(list, track, used, count, res, i + 1, length, isGroup, need, max, validator);
    used[c.direction]--;
    count[c.name]--
    track.pop();
  }
}
// 深度优先
const DFS = function(list, length, isGroup, need, max, validator) {
  let res = [];
  let track = [];
  let used = {
    左: 0,
    上: 0,
    右: 0,
  };
  let count = {};
  backtrack(list, track, used, count, res, 0, length, isGroup, need, max, validator);
  return res;
}

// 广度优先
const BFS = function (list, length, isGroup, need, max, validator) {
  if(!list.length) return [];
  let q = [Array.from({length: length}).fill(-1)]; // 记录 每个机芯的 index  [-1,-1,-1,-1,-1,-1] 每个index 依次 递增直到 取完list;
  let res = [];
  let visited = {};
  while(q.length) {
    if(res.length > max) return res; // 组合太多了
    for(let i = 0; i< q.length; i++) {
      let cur = q.shift();
      let combin  = getDataByIndexs([...cur], list)
      let condition = validConditon(getDataByIndexs([...cur], list), isGroup, need);
      if(condition && validator(combin)) {
        res.push(handleCombin(combin));
      }
      for(let j = 0; j < length; j++) {
        let indexs = nextIndexs([...cur], j, list.length);
        if(isVisited([...indexs], visited)) continue;
        if(isRepeatIndex(indexs)) continue;
        addVisited([...indexs], visited);
        q.push([...indexs])
      }
    }
  }
  return res;
}
const getDataByIndexs = function(indexs, list) {
  indexs = indexs.filter( i =>  i >= 0);
  return indexs.map( i => list[i]);
}
const nextIndexs= function (indexs, j, listLength) {
  if(indexs[j] < listLength - 1 ) {
    indexs[j] += 1;
  } 
  return indexs;
}
const isVisited = function(indexs, visited) {
  let key = indexs.sort().join('');
  return visited[key]
}
const isRepeatIndex = function (indexs) {
  let obj = {}
  for(let i = 0; i < indexs.length; i++) {
    let j = indexs[i] + '';
    obj[j] = (obj[j]  || 0) + 1;
    if(obj[j] > 1 && j !== '-1') return true;
  }
  return false;
}
const addVisited = function (indexs, visited) {
  let key = indexs.sort().join('');
  visited[key] = true;
}
const validConditon = function(combinData, isGroup, need) {
  // 每个位置最多 2个
  let used = {
    左: 0,
    上: 0,
    右: 0,
  };
  let count = {};
  for( let i = 0; i < combinData.length; i++) {
    let data = combinData[i];
    used[data.direction]++;
    if(used[data.direction] > 2) return false;
    if(isGroup) {
      count[data.name] = (count[data.name] || 0) + 1;
      if(count[data.name] > need[data.name]) return false;
    }
  }
  return true;
}
export {
  BFS,
  DFS,
}